package DuiLie;

import List.SinNode;

// LinkQueue类实现了IQueue接口，用于表示一个链式队列结构
// 链式队列是一种数据结构，它遵循先进先出（FIFO）的原则来存储和操作数据元素
// 就像排队一样，先进入队列的元素先被处理
public class LinkQueue implements IQueue {

    // 以下是LinkQueue类的成员变量

    // front用于指向队列的队首节点
    // 队首节点是队列中最先进入的元素所在的节点（除了可能存在的一个空的头节点之外）
    public SinNode front;

    // rear用于指向队列的队尾节点
    // 队尾节点是队列中最后进入的元素所在的节点
    public SinNode rear;

    // length用于记录当前队列中元素的个数
    public int length;

    // 构造函数，用于创建一个最大存储单元个数为maxSize的空队列
    // 这里实际上先创建了一个空的头节点，然后让front和rear都指向这个头节点
    // 此时队列中还没有实际存储的数据元素，长度为0
    public LinkQueue(int maxSize) {
        // 创建一个SinNode类型的空节点作为队列的头节点
        // 这个头节点不存储实际的数据，主要是为了方便操作队列
        this.front = new SinNode();
        // 让队尾指针rear也指向刚创建的这个头节点，因为此时队列是空的
        this.rear = this.front;
        // 初始化队列长度为0，表示当前队列中没有实际的数据元素
        this.length = 0;
    }

    // clear方法用于将队列置空
    // 它的主要操作是遍历整个链表（除了头节点），将每个节点之间的连接断开
    // 这样这些节点就可以被Java的垃圾回收机制回收，释放内存空间
    // 最后再将队首和队尾指针重新设置为初始的空队列状态
    public void clear() {
        // 先从队首节点的下一个节点开始遍历，因为头节点不存储实际数据
        SinNode p = front.getNext();
        while (p!= null) {
            // 保存当前节点p的下一个节点，以便后续继续遍历
            SinNode next = p.getNext();
            // 将当前节点p的下一个节点引用设置为null，断开与后面节点的连接
            p.setNext(null);
            // 将p指针移动到下一个节点，继续遍历
            p = next;
        }

        // 将队首节点的下一个节点引用设置为null，确保队首节点也处于初始的空状态
        front.setNext(null);
        // 让队尾指针rear重新指向队首节点，此时队列又回到了空队列的状态
        rear = front;
        // 将队列长度设置为0，表示队列已经被清空
        length = 0;
    }

    // isEmpty方法用于判断队列是否为空
    // 它通过比较队列的长度是否为0来确定队列是否为空队列
    // 如果长度为0，就说明队列中没有实际的数据元素，即为空队列
    public boolean isEmpty() {
        // 返回队列长度是否等于0的判断结果
        return this.length == 0;
    }

    // length方法用于返回队列的长度
    // 也就是当前队列中实际存储的数据元素的个数
    public int length() {
        return this.length;
    }

    // peek方法用于读取队首元素并返回其值
    // 但是要注意，如果队列是空的，就不能读取队首元素，此时会抛出QueueEmptyException异常
    public Object peek() throws QueueEmptyException {
        // 先判断队列长度是否小于1，如果是，说明队列是空的
        if (this.length < 1) {
            // 抛出QueueEmptyException异常，并给出相应的错误提示信息
            throw new QueueEmptyException("错误，队列为空");
        }

        // 如果队列不为空，就返回队首节点（注意这里是front.getNext()，因为front指向头节点）的数据值
        return this.front.getNext().getData();
    }

    // offer方法用于将一个元素入队，也就是将元素添加到队列的末尾
    // 它会创建一个新的SinNode节点来存储要入队的元素，并将其添加到队列的尾部
    public void offer(Object x) throws Exception {
        // 创建一个新的SinNode节点，将传入的元素x作为节点的数据存储起来
        // 新节点的下一个节点引用先设置为null，因为它是要添加到队尾的
        SinNode p = new SinNode(x, null);
        // 将队尾节点rear的下一个节点引用指向新创建的节点p
        // 这样就把新节点添加到了队列的末尾
        rear.setNext(p);
        // 然后让队尾指针rear指向新添加的节点p，因为现在p成为了新的队尾节点
        this.rear = p;
        // 将队列的长度加1，表示队列中又多了一个元素
        this.length++;
    }

    // poll方法用于将队首元素出队，也就是移除队列头部的元素并返回其值
    // 同样要注意，如果队列是空的，就不能进行出队操作，此时会抛出QueueEmptyException异常
    public Object poll() throws QueueEmptyException {
        // 先判断队列长度是否小于1，如果是，说明队列是空的
        if (this.length < 1) {
            // 抛出QueueEmptyException异常，并给出相应的错误提示信息
            throw new QueueEmptyException("错误，队列为空");
        }
        // 获取队首节点（这里是front.getNext()，因为front指向头节点）
        SinNode p = this.front.getNext();
        // 将队首节点front的下一个节点引用指向当前队首节点p的下一个节点
        // 这样就相当于移除了原来的队首节点p
        front.setNext(p.getNext());
        // 将队列的长度减1，表示队列中少了一个元素
        this.length--;
        // 如果出队操作后队列变为空队列了（即长度为0）
        if (this.isEmpty()) {
            // 让队尾指针rear重新指向队首节点front，回到空队列的状态
            this.rear = this.front;
        }
        // 返回被移除的队首节点p的数据值
        return p.getData();
    }

    // display方法用于输出队列中的所有数据元素
    // 如果队列是空的，就输出相应的提示信息“队列为空”，然后直接返回，不进行后续输出操作
    public void display() {
        // 先判断队列是否为空，如果是，就输出提示信息并返回
        if (isEmpty()) {
            System.out.println("队列为空");
            return;
        }
        // 创建一个StringBuilder对象，用于高效地拼接字符串
        StringBuilder sb = new StringBuilder();
        // 从队首节点的下一个节点开始遍历队列（因为头节点不存储实际数据）
        SinNode p = this.front.getNext();
        // 先在拼接的字符串中添加一个左方括号，作为输出元素列表的开头
        sb.append("[");
        while (p!= null) {
            // 将当前节点p的数据值添加到拼接的字符串中
            sb.append(p.getData());
            // 将指针p移动到下一个节点，继续遍历
            p = p.getNext();
            // 如果下一个节点不为空，就在拼接的字符串中添加一个逗号，用于分隔不同的元素
            if (p!= null) {
                sb.append(",");
            }
        }
        // 在拼接的字符串末尾添加一个右方括号，作为输出元素列表的结尾
        sb.append("]");
        // 输出拼接好的包含队列所有元素的字符串
        System.out.println(sb.toString());
    }
}